package main

import (
	"fmt"
	"math/rand"
	"time"
)

func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}
func heapify(arr []int, i, length int) {
	left := 2*i + 1
	right := 2*i + 2
	largest := i
	if left < length && arr[left] > arr[largest] {
		largest = left
	}
	if right < length && arr[right] > arr[largest] {
		largest = right
	}
	if largest != i {
		swap(arr, i, largest)
		heapify(arr, largest, length)
	}
}
func buildMaxHeap(arr []int) {
	length := len(arr)
	for i := length / 2; i >= 0; i-- {
		heapify(arr, i, length)
	}
}
func heapSort(arr []int) []int {
	length := len(arr)
	buildMaxHeap(arr)
	for i := length - 1; i >= 0; i-- {
		swap(arr, 0, i)
		length--
		heapify(arr, 0, length)
	}
	return arr
}

func main() {
	arr := make([]int, 100)
	rand.Seed(time.Now().UnixNano())

	length := len(arr)
	for i := 0; i < length; i++ {
		arr[i] = rand.Intn(1000)
	}
	fmt.Println(arr)
	fmt.Println(heapSort(arr))
}
